package com.algomypractice.sort.timecomplexityon2;

import com.annotation.service.SortTest;

/**
 * @author: ZhouBert
 * @date: 2019/6/14
 * @description: 快速排序（冒泡排序升级版）
 * http://www.sohu.com/a/246785807_684445
 * 漫画解析
 */
public class QuickSort {

	/**
	 * 快速排序
	 * 挖坑法
	 */
	@SortTest
	public static void quickSortByDigHole(int[] arr) {
		quickSortByDigHole(arr, 0, arr.length - 1);
	}

	/**
	 * 快速排序
	 * 交换指针
	 * @param arr
	 */
	public static void quickSortBySwapPoint(int[] arr){

	}

	private static void quickSortByDigHole(int[] arr, int startIndex, int endIndex) {
		///递归结束条件：startIndex 大于等于 endIndex 时
		if (startIndex >= endIndex) {
			return;
		}
		//得到基准元素位置
		int pivotIndex = partitionByDigHole(arr, startIndex, endIndex);
		// 用分治法递归数列的两部分
		quickSortByDigHole(arr, startIndex, pivotIndex - 1);
		quickSortByDigHole(arr, pivotIndex + 1, endIndex);
	}

	private static void quickSortBySwapPoint(int[] arr, int startIndex, int endIndex){
		//
		if (startIndex >= endIndex) {
			return;
		}
	}

	private static int partitionByDigHole(int[] arr, int startIndex, int endIndex) {
		//取第一个位置的元素作为基准元素
		int pivot = arr[startIndex];
		int left = startIndex;
		int right = endIndex;
		//坑的位置，初试等于pivot的位置
		int index = startIndex;
		//大循环结束 在左右指针重合或者交错时
		while (right >= left) {
			//right 指针从右向左进行比较
			while (right >= left) {
				if (arr[right] < pivot) {
					arr[left] = arr[right];
					index = right;
					left++;
					break;
				}
				right--;
			}
			//left 指针从左向右进行比较
			while (right >= left) {
				if (arr[left] > pivot) {
					arr[right] = arr[left];
					index = left;
					right--;
					break;
				}
				left++;
			}
		}
		arr[index] = pivot;
		return index;
	}
}
